package com.Algorithm.HUAWEI.two20220303;

import com.TestDemo.Test2.IFTest;

import java.security.spec.ECField;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/03/16/14:19
 * @Description:
 * @Target:
 */
public class 素数伴侣 {
/*
* 题目描述
    若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。
    * 现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，
    * 挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，
    * 而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

    输入:
    有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

    输出:
    输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
    数据范围： 1≤n≤100  ，输入的数据大小满足 2≤val≤30000
    输入描述：
    输入说明
    1 输入一个正偶数 n
    2 输入 n 个整数

    输出描述：
    求得的“最佳方案”组成“素数伴侣”的对数。
    *
    * 输入：
        4
        2 5 6 13
        2
        3 6
        输出：
        2
        0
        *
        *
        示例2
        输入：
        2
        3 6
        输出：
        0

*
* */
// 3 8 9 12 20

//    12
//20867 25786 13932 11112 18239 25481 2607 8855 9788 28461 27950 9814
    // 4

    public static void main(String[] args) {
        // 先使用从小的开始配对,
        Scanner in = new Scanner(System.in);
     while (in.hasNextLine()){
            String ss1 = in.nextLine();
            String[] ss2 = in.nextLine().split(" ");;

            System.out.println(execute(ss2));}
/*
        HashSet set = new HashSet();
        for (String s : ss2) {
            if (hasOneOrMore(Integer.valueOf(s),ss2)>0){
                set.add(s);
            }

*/
/*           if (>0){
//               System.out.println(s);
           }*//*

        }
*/


//        System.out.println("---------------------------------------");
//        set.forEach(System.out::println);





    }

    // 将进入的数据进行处理,并运行,最后返回count
    static int execute(String[] ss2){

        int count = 0;

        // 奇数list
        ArrayList<Integer> OddList = new ArrayList();
        // 偶数list
        ArrayList<Integer> EvenList = new ArrayList();

        for (String s : ss2) {
            System.out.print(s+" ");
            if (Integer.valueOf(s)%2==0){
                EvenList.add(Integer.valueOf(s));

            }else {
                OddList.add(Integer.valueOf(s));
            }
        }

        System.out.println();
        // 奇数进偶数匹配.偶数匹配对数组
        int[] Match  = new int[EvenList.size()];

        for (Integer integer : OddList) {
            // 对应偶数集合的标记
            boolean[] Mark  = new boolean[EvenList.size()];
            if (find(integer, EvenList,Match,Mark)){
                count++;
            }
        }

        for (int i = 0; i < Match.length; i++) {
            System.out.println(Match[i]+" "+EvenList.get(i));
        }




        return count;

    }

  // 匈牙利的目标就是将两组数,先变成一组数
   // 匈牙利算法要素,1.进入的待匹配的数 2.匹配数集合 3.匹配对(对应匹配数,有就是匹配值,无就是0)集合 4.标记是否匹配过.
    // 作为过程处理器,目标:只将经过记录.

    // 我一个数,进来的时候,第一先看偶数遍历标记,如果有之前经过的,那么就下一个.  第二看能不能进入匹配对,---先来占坑,后来让路(不能就不让)//标记的核心..
    static boolean find(int x,ArrayList<Integer> list,int[] Match,boolean[] Mark){
        boolean flag = false;
        for (int i = 0; i < list.size(); i++) {
            if (isSuShu(x+list.get(i))&&Mark[i]==false){
                Mark[i] = true;

                if (Match[i]==0||find(Match[i],list,Match,Mark)){
                    Match[i] = x;
                    flag = true;
                    break;
                }
            }
        }

        return flag;
    }

    // 素数
    static boolean isSuShu(int i){
        boolean flag = true;

        if (i<=1){
            flag = false;
        }
        if (i==2){
            flag = true;
        }

        if (flag == true){

        for (int j = 2; j <= Math.sqrt(i)+1; j++) {
            if (i%j==0){
                flag = false;
            }
        }

        }
        return flag;
    }

}
